package cxydmmszl.chapter04.t061;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * <li style="color: red;">Prob</li>
 * 打气球的最大分数
 * <li style="color: red;">Desc</li>
 * 给定一个数组 arr,长度为 n。代表排有分数的气球。
 * 每打爆一个气球都能获得分数，假设打爆气球的分数为 X，获得分数的规则如下：<br/>
 * &emsp;1) 如果被打爆气球的左边有没被打爆的气球，找到离被打爆气球最近的气球，假设分数为 L；
 * 如果被打爆气球的右边有没被打爆的气球，找到离被打爆气球最近的气球，假设分数为 R。获得分数为 L*X*R。<br/>
 * &emsp;2) 如果被打爆的气球的左边有没被打爆的气球，找到离被打爆气球最近的气球，假设分数为 L；
 * 如果被打爆气球的右边所有气球都已经被打爆，获得分数为 L*X。<br/>
 * &emsp;3) 如果被打爆气球的左边所有的气球都已经被打爆；
 * 如果被打爆气球的右边有没被打爆的气球，找到离被打爆气球最近的气球。获得分数为 X*R。<br/>
 * &emsp;4) 如果被打爆气球的左边和右边所有的气球都已经被打爆。获得分数为 X。<br/>
 * 目标是打爆所有气球，获得每次打爆的分数。通过选择打爆气球的顺序，可以得到不同的总分，请返回能获得的最大分数。<br/><br/>
 * 输入描述：<br/>
 * 输出包括两行，第一行包括一个整数 n(0<=n<=500)，第二行包括 n个整数，代表数组 arr(1<=arr[i]<=100)。<br/><br/>
 * 输出描述：<br/>
 * 输出包括一个整数，代表可能获得的最大分数。
 * <li style="color: red;">Link</li> CD20
 *
 * @author habitplus
 * @since 2021-09-02 09:27
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        int[] arr = new int[n];
        String[] ss = bf.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(ss[i]);
        }

        int ans = maxBalloonScore2(arr);
        System.out.println(ans);

    }

    private static int maxBalloonScore2(int[] arr) {
        if (arr == null || arr.length < 1) {
            return 0;
        }
        int n = arr.length;
        if (n == 1) {
            return arr[0];
        }

        // 扩展 arr
        int[] help = new int[n + 2];
        System.arraycopy(arr, 0, help, 1, n);
        help[0] = help[n + 1] = 1;

        // dp[i][j] 表示 打爆 arr[i...j] 上所有气球所得的最大分数
        int[][] dp = new int[n + 2][n + 2];

        for (int i = 1; i <= n; i++) {
            dp[i][i] = help[i - 1] * help[i] * help[i + 1];
        }

        for (int i = n; i > 0; i--) {
            for (int j = i + 1; j <= n; j++) {
                int finalL = help[i - 1] * help[i] * help[j + 1] + dp[i + 1][j];
                int finalR = help[i - 1] * help[j] * help[j + 1] + dp[i][j - 1];
                dp[i][j] = Math.max(finalL, finalR);

                for (int k = i + 1; k < j; k++) {
                    dp[i][j] = Math.max(dp[i][j],
                            dp[i][k - 1] + dp[k + 1][j] + help[i - 1] * help[j + 1] * help[k]);
                }
            }
        }

        return dp[1][n];
    }

    private static int maxBalloonScore1(int[] arr) {
        if (arr == null || arr.length < 1) {
            return 0;
        }
        int n = arr.length;
        if (n == 1) {
            return arr[0];
        }

        // 扩展 arr
        int[] help = new int[n + 2];
        System.arraycopy(arr, 0, help, 1, n);
        help[0] = help[n + 1] = 1;

        return process1(help, 1, n);
    }

    private static int process1(int[] arr, int l, int r) {
        // 如果 只有一个气球，直接打爆即可
        if (l == r) {
            return arr[l - 1] * arr[l] * arr[r + 1];
        }

        int max = Math.max(arr[l - 1] * arr[l] * arr[r + 1] + process1(arr, l + 1, r),
                arr[l - 1] * arr[r] * arr[r + 1] + process1(arr, l, r - 1));

        for (int i = l + 1; i < r; i++) {
            max = Math.max(max,
                    arr[l - 1] * arr[r + 1] * arr[i] + process1(arr, l, i - 1) + process1(arr, i + 1, r));
        }
        return max;
    }


}
